Search for: All records

Concurrency bugs are extremely difficult to detect. Recently, several dynamic techniques achieve sound analysis. M2 is even complete for two threads. It is designed to decide whether two events can occur consecutively. However, real-world concurrency bugs can involve more events and threads. Some can occur when the order of two or more events can be exchanged even if they occur not consecutively. We propose a new technique SeqCheck to soundly decide whether a sequence of events can occur in a specified order. The ordered sequence represents a potential concurrency bug. And several known forms of concurrency bugs can be easily encoded into event sequences where each represents a way that the bug can occur. To achieve it, SeqCheck explicitly analyzes branch events and includes a set of efficient algorithms. We show that SeqCheck is sound; and it is also complete on traces of two threads. We have implemented SeqCheck to detect three types of concurrency bugs and evaluated it on 51 Java benchmarks producing up to billions of events. Compared with M2 and other three recent sound race detectors, SeqCheck detected 333 races in ~30 minutes; while others detected from 130 to 285 races in ~6 to ~12 hours. SeqCheck detected 20 deadlocks in ~6 seconds. This is only one less than Dirk; but Dirk spent more than one hour. SeqCheck also detected 30 atomicity violations in ~20 minutes. The evaluation shows SeqCheck can significantly outperform existing concurrency bug detectors. 

Multithreaded programs can have deadlocks, even after deployment, so users may want to run deadlock tools on deployed programs. However, current deadlock predictors such as MagicLock and UnDead have large overheads that make them impractical for end-user deployment and confine their use to development time. Such overhead stems from running an exponential-time algorithm on a large execution trace. In this paper, we present the first low-overhead deadlock predictor, called AirLock, that is fit for both in-house testing and deployed programs. AirLock maintains a small predictive lock reachability graph, searches the graph for cycles, and runs an exponential-time algorithm only for each cycle. This approach lets AirLock find the same deadlocks as MagicLock and UnDead but with much less overhead because the number of cycles is small in practice. Our experiments with real-world benchmarks show that the average time overhead of AirLock is 3.5%, which is three orders of magnitude less than that of MagicLock and UnDead. AirLock's low overhead makes it suitable for use with fuzz testers like AFL and on-the-fly after deployment. 

Middle to Late Pleistocene human evolution in East Asia has remained controversial regarding the extent of morphological continuity through archaic humans and to modern humans. Newly found ∼300,000-y-old human remains from Hualongdong (HLD), China, including a largely complete skull (HLD 6), share East Asian Middle Pleistocene (MPl) human traits of a low vault with a frontal keel (but no parietal sagittal keel or angular torus), a low and wide nasal aperture, a pronounced supraorbital torus (especially medially), a nonlevel nasal floor, and small or absent third molars. It lacks a malar incisure but has a large superior medial pterygoid tubercle. HLD 6 also exhibits a relatively flat superior face, a more vertical mandibular symphysis, a pronounced mental trigone, and simple occlusal morphology, foreshadowing modern human morphology. The HLD human fossils thus variably resemble other later MPl East Asian remains, but add to the overall variation in the sample. Their configurations, with those of other Middle and early Late Pleistocene East Asian remains, support archaic human regional continuity and provide a background to the subsequent archaic-to-modern human transition in the region.